The need for resource allocation decisions arises in a broad range of technological and industrial areas such as, for example, the assignment of transmission facilities in telephone transmission systems, inventory control, materials and operations management, as the routing of data services between related business offices. Resource allocation in this context means, in general, the deployment of specific technological or industrial resources for the production of particular technological or industrial results.
Resource allocation decisions are typically subject to constraints on such allocations. Resources are always limited in overall availability, and, furthermore, the usefulness of a particular resource in some particular application may also be limited. The problem, then, is to allocate the resources so as to satisfy all of the constraints and, simultaneously, to maximize the payoff, i.e., minimize the costs or maximize the benefits.
One method of solving resource allocation problems includes translating the resource allocation (or optimization) problem into a linear programming model. Such a model consists of a number of linear expressions that represent the quantitative relationships among allocations and constraints. The formal statement of a linear programming model takes the form of an objective function which is to be maximized or minimized, and a plurality of constraint relationships which express the physical constraints on acceptable allocations. The objective function and constraint relationships can be expressed in compact mathematical equations and definitions.
All objective functions and all constraint relationships can then be translated into linear programming format by algebraic manipulation. A known method of performing the required algebraic manipulation includes defining index variables and their properties, e.g., names, ranges and bounds, etc., and recording the same utilizing a symbol table during a syntax analysis phase. Subsequently, when an index variable is used as a range variable, its definition may be looked up and retrieved from a symbol table, as shown, for example, in FIG. 1. A temporary data record may then be created to hold the relevant definition information, plus any other relevant information that is necessary to carry out the desired expansion task.
With this approach, the temporary data record would need to contain certain amount of information that is redundant since the information is already stored in the symbol table. At a minimum, multiple copies of variable names must be kept in order to support name-based searches for uses of variables in algebraic expressions.
Other similar occurrences of redundancy are sometimes introduced during operation. For example, when two or more index variables are used to define a compound range, their records are usually linked together in a chronological order, which often times does not result in the most efficient way of processing them.
The known prior art fails to disclose an approach to algebraic modeling of an optimization problem that eliminates the need to keep redundant information regarding index variables during the expansion process.
Consequently, a need has developed for a means for efficiently translating an optimization problem which maximizes memory usage.